package com.yanceysong.codetop.s11_s20;

/**
 * @ClassName S14_Mid_200_岛屿数量
 * @Description
 * @date 2025/8/17 22:50
 * @Author yanceysong
 * @Version 1.0
 */
public class S14_Mid_200_岛屿数量 {
    /**
     * LeetCode链接
     * <a href="https://leetcode.cn/problems/number-of-islands/">...</a>
     * <p>
     * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * 此外，你可以假设该网格的四条边均被水包围。
     * <p>
     * ==================== 岛屿数量算法图解 ====================
     * <p>
     * 算法思路：深度优先搜索 (DFS) / 沉岛思想
     * 1. 遍历网格：从左到右，从上到下遍历整个二维网格。
     * 2. 发现陆地：当遇到一个 '1'（陆地）时，说明我们发现了一个新岛屿，岛屿数量加一。
     * 3. 沉岛操作：从这个 '1' 开始，使用深度优先搜索（DFS）将所有与之相连的陆地（'1'）都标记为 '0'（水）。
     * 这个过程相当于将整个岛屿“淹没”，以防止重复计数。
     * 4. 继续遍历：继续遍历网格，直到所有格子都被访问过。
     * <p>
     * 执行示例：
     * grid = [
     * .  ['1','1','0','0','0'],
     * .  ['1','1','0','0','0'],
     * .  ['0','0','1','0','0'],
     * .  ['0','0','0','1','1']
     * .]
     * <p>
     * 遍历过程：
     * 1. `(0,0)` 是 '1' -> 发现第1个岛屿。`islandCount = 1`。
     * - 从 `(0,0)` 开始DFS，将所有相连的 '1' 变为 '0'。
     * - 网格变为:
     * .     ['0','0','0','0','0'],
     * .     ['0','0','0','0','0'],
     * .     ['0','0','1','0','0'],
     * .     ['0','0','0','1','1']
     * 2. 继续遍历，直到 `(2,2)` 是 '1' -> 发现第2个岛屿。`islandCount = 2`。
     * .   - 从 `(2,2)` 开始DFS。
     * .   - 网格变为:
     * .     ['0','0','0','0','0'],
     * .     ['0','0','0','0','0'],
     * .     ['0','0','0','0','0'],
     * .     ['0','0','0','1','1']
     * 3. 继续遍历，直到 `(3,3)` 是 '1' -> 发现第3个岛屿。`islandCount = 3`。
     * .   - 从 `(3,3)` 开始DFS。
     * .   - 网格变为:
     * .     ['0','0','0','0','0'],
     * .     ['0','0','0','0','0'],
     * .     ['0','0','0','0','0'],
     * .     ['0','0','0','0','0']
     * <p>
     * 最终结果：`islandCount = 3`
     * <p>
     * ===============================================================
     */
    public int numIslands(char[][] grid) {
        // 边界检查
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int numRows = grid.length;
        int numCols = grid[0].length;
        int islandCount = 0;

        // 遍历网格中的每个单元格
        for (int row = 0; row < numRows; ++row) {
            for (int col = 0; col < numCols; ++col) {
                // 如果当前单元格是陆地 '1'
                if (grid[row][col] == '1') {
                    // 发现一个新岛屿，计数器加一
                    islandCount++;
                    // 使用DFS将该岛屿的所有部分淹没（标记为 '0'）
                    exploreIslandDFS(grid, row, col);
                }
            }
        }

        return islandCount;
    }

    /**
     * 深度优先搜索，探索并淹没一个岛屿
     *
     * @param grid 网格
     * @param row  当前行
     * @param col  当前列
     */
    private void exploreIslandDFS(char[][] grid, int row, int col) {
        int numRows = grid.length;
        int numCols = grid[0].length;

        // 递归终止条件：
        // 1. 越界 (行或列超出网格范围)
        // 2. 遇到水 '0' (已经是水域，无需操作)
        if (row < 0 || col < 0 || row >= numRows || col >= numCols || grid[row][col] == '0') {
            return;
        }

        // 淹没当前陆地单元格，将其标记为 '0'，防止重复访问
        grid[row][col] = '0';

        // 向四个方向递归探索
        exploreIslandDFS(grid, row - 1, col); // 上
        exploreIslandDFS(grid, row + 1, col); // 下
        exploreIslandDFS(grid, row, col - 1); // 左
        exploreIslandDFS(grid, row, col + 1); // 右
    }

    public static void main(String[] args) {
        S14_Mid_200_岛屿数量 solution = new S14_Mid_200_岛屿数量();

        System.out.println("=== 岛屿数量测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同形状岛屿测试
        System.out.println("\n--- 测试3: 不同形状岛屿测试 ---");
        testDifferentShapes(solution);

        // 测试4: 特殊情况测试
        System.out.println("\n--- 测试4: 特殊情况测试 ---");
        testSpecialCases(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S14_Mid_200_岛屿数量 solution) {
        // 示例1
        char[][] grid1 = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        testNumIslands(solution, grid1, 1, "题目示例1");

        // 示例2
        char[][] grid2 = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        testNumIslands(solution, grid2, 3, "题目示例2");

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S14_Mid_200_岛屿数量 solution) {
        // 测试1: null grid
        testNumIslands(solution, null, 0, "null grid");

        // 测试2: 空 grid
        char[][] grid2 = {};
        testNumIslands(solution, grid2, 0, "空 grid");

        // 测试3: 1x1 grid - 陆地
        char[][] grid3 = {{'1'}};
        testNumIslands(solution, grid3, 1, "1x1 grid - 陆地");

        // 测试4: 1x1 grid - 水
        char[][] grid4 = {{'0'}};
        testNumIslands(solution, grid4, 0, "1x1 grid - 水");

        // 测试5: 单行
        char[][] grid5 = {{'1', '1', '0', '1'}};
        testNumIslands(solution, grid5, 2, "单行");

        // 测试6: 单列
        char[][] grid6 = {{'1'}, {'0'}, {'1'}, {'1'}};
        testNumIslands(solution, grid6, 2, "单列");

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同形状的岛屿
     */
    private static void testDifferentShapes(S14_Mid_200_岛屿数量 solution) {
        // 测试1: L形岛屿
        char[][] grid1 = {
                {'1', '0', '0'},
                {'1', '0', '0'},
                {'1', '1', '1'}
        };
        testNumIslands(solution, grid1, 1, "L形岛屿");

        // 测试2: U形岛屿
        char[][] grid2 = {
                {'1', '0', '1'},
                {'1', '1', '1'}
        };
        testNumIslands(solution, grid2, 1, "U形岛屿");

        // 测试3: 对角线相邻（不构成岛屿）
        char[][] grid3 = {
                {'1', '0', '0'},
                {'0', '1', '0'},
                {'0', '0', '1'}
        };
        testNumIslands(solution, grid3, 3, "对角线相邻");

        System.out.println("✓ 不同形状岛屿测试通过");
    }

    /**
     * 测试特殊情况
     */
    private static void testSpecialCases(S14_Mid_200_岛屿数量 solution) {
        // 测试1: 全是陆地
        char[][] grid1 = {
                {'1', '1', '1'},
                {'1', '1', '1'}
        };
        testNumIslands(solution, grid1, 1, "全是陆地");

        // 测试2: 全是水
        char[][] grid2 = {
                {'0', '0', '0'},
                {'0', '0', '0'}
        };
        testNumIslands(solution, grid2, 0, "全是水");

        System.out.println("✓ 特殊情况测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S14_Mid_200_岛屿数量 solution) {
        // 测试1: 中等规模
        System.out.println("性能测试1: 50x50 grid");
        testPerformanceCase(solution, 50, 50);

        // 测试2: 较大规模
        System.out.println("性能测试2: 100x100 grid");
        testPerformanceCase(solution, 100, 100);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S14_Mid_200_岛屿数量 solution, int rows, int cols) {
        char[][] grid = new char[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grid[i][j] = (Math.random() > 0.5) ? '1' : '0';
            }
        }
        long startTime = System.currentTimeMillis();
        int count = solution.numIslands(grid);
        long endTime = System.currentTimeMillis();

        System.out.println("  Grid大小: " + rows + "x" + cols + ", 发现 " + count + " 个岛屿, 执行时间: " + (endTime - startTime) + "ms");
        assert (endTime - startTime) < 500 : "性能测试：执行时间过长";
    }

    /**
     * 测试岛屿数量的辅助方法
     */
    private static void testNumIslands(S14_Mid_200_岛屿数量 solution, char[][] grid, int expected, String description) {
        // 创建grid的副本，因为原grid会被修改
        char[][] gridCopy = copyGrid(grid);
        int actual = solution.numIslands(gridCopy);

        System.out.print(description + " -> 输出: " + actual);
        System.out.println(" (期望: " + expected + ")");

        assert actual == expected : description + "测试失败";
    }

    /**
     * 复制grid的辅助方法
     */
    private static char[][] copyGrid(char[][] grid) {
        if (grid == null) return null;
        char[][] newGrid = new char[grid.length][];
        for (int i = 0; i < grid.length; i++) {
            if (grid[i] == null) continue;
            newGrid[i] = new char[grid[i].length];
            System.arraycopy(grid[i], 0, newGrid[i], 0, grid[i].length);
        }
        return newGrid;
    }
}

